package lib

//link to 292 294
func init() {
	Probs = append(Probs, Problem{
		Num:         464,
		Discription: "100-Game(两个人分别不放回从1...max里不放回选一个数，先使得一起选取的数之和target超过指定的人获胜，给定max,target，判断双方最佳决策下先手者是否能获胜)",
		Level:       2,
		Labels: map[string]int{
			"记忆化搜索":   1,
			"二进制状态表示": 1,
		},
	})
}

func CanIWin(maxChoosableInteger int, desiredTotal int) bool {
	//如果所有数加起来都没指定值大，判为两方玩家都输
	if (maxChoosableInteger+1)*maxChoosableInteger/2 < desiredTotal {
		return false
	}

	//记录在某个数字使用状态下，先手玩家是否能赢
	stateMap := make(map[int]bool, 0)
	var dfs func(int, int) bool
	//usedMap：二进制表示的1...maxChoosableInteger使用情况
	//curNum：当前两边选的数之和
	dfs = func(usedMap int, curSum int) bool {
		canWin, exist := stateMap[usedMap]
		if exist {
			return canWin
		}

		for i := 1; i <= maxChoosableInteger; i++ {
			if usedMap&(1<<(i-1)) != 0 {
				continue
			}

			if curSum+i >= desiredTotal || !dfs(usedMap|(1<<(i-1)), curSum+i) {
				stateMap[usedMap] = true
				return true
			}
		}

		stateMap[usedMap] = false
		return false
	}

	return dfs(0, 0)
}
